package com.lc.lc421;

public class Main {

}

class Tire {
	Tire left = null;
	Tire right = null;
}


class Solution {
	int Max = 30;
	Tire root = new Tire();
	
	void add(int x) {
		Tire cur = root;
		for (int i = Max; i >= 0; i --) {
			int dig = (x >> i) & 1;
			if (dig == 0) {
				if (cur.left == null) {
					cur.left = new Tire();
				}
				cur = cur.left;
			} else {
				if (cur.right == null) {
					cur.right = new Tire();
				}
				cur = cur.right;
			}
		}
	}
	
	int check(int num) {
		Tire cur = root;
		int x = 0;
		for (int k = Max; k >= 0; k --) {
			int dig = (num >> k) & 1;
			if (dig == 1) {
				if (cur.left != null) {
					cur = cur.left;
					x = 2 * x + 1;
				} else {
					cur = cur.right;
					x = 2 * x;
				}
			} else {
				if (cur.right != null) {
					cur = cur.right;
					x = 2 * x + 1;
				} else {
					cur = cur.left;
					x = 2 * x;
				}
			}
		}
		return x;
	}

    public int findMaximumXOR(int[] nums) {
    	int res = 0;
    	for (int i = 1; i <= nums.length; i ++) {
    		add(nums[i - 1]);
    		res = Math.max(res, check(nums[i]));
    	}
    	return res;
    }
}
